/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package dataStructure;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 *
 * @author azouz
 */
public class Sorting {

    static void insertSort(int[] data) {
        for (int i = 0; i <= data.length; i++) {
            int j = i;
            while (j > 0 && data[i] < data[j - 1]) {
                j--;
            }
            int tmp = data[i];
            for (int k = i; k > j; k--) {
                data[k] = data[k - 1];
            }
            data[j] = tmp;
        }
    }

    static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                // update min when finding a smaller element
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }

            // put the smallest element at position i
            swap(arr, i, min);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static ArrayList<Integer> quickSort(ArrayList<Integer> arr) {
        if (arr.isEmpty()) {
            return arr;
        }
        ArrayList<Integer> less = new ArrayList<Integer>();
        ArrayList<Integer> greater = new ArrayList<Integer>();
        ArrayList<Integer> equal = new ArrayList<Integer>();
        int pivot = arr.get(arr.size() / 2);
        for (int i : arr) {
            if (i == pivot) {
                equal.add(i);
            }
            if (i > pivot) {
                greater.add(i);
            }
            if (i < pivot) {
                less.add(i);
            }
        }
        less = quickSort(less);
        greater = quickSort(greater);
        less.addAll(equal);
        less.addAll(greater);
        return less;
    }

    public static <E extends Comparable<? super E>> List<E> mergeSort(List<E> m) {
        if (m.size() <= 1) {
            return m;
        }

        int middle = m.size() / 2;
        List<E> left = m.subList(0, middle);
        List<E> right = m.subList(middle, m.size());

        right = mergeSort(right);
        left = mergeSort(left);
        List<E> result = merge(left, right);

        return result;
    }

    public static <E extends Comparable<? super E>> List<E> merge(List<E> left, List<E> right) {
        List<E> result = new ArrayList<E>();
        Iterator<E> leftIterator = left.iterator();
        Iterator<E> rightIterator = right.iterator();

        E leftObject = leftIterator.next();
        E rightObject = rightIterator.next();
        System.out.println(leftObject);
        System.out.println(rightObject);
        while (true) {
            //change the direction of this comparison to change the direction of the sort
            if (leftObject.compareTo(rightObject) <= 0) {
                result.add(leftObject);
                if (leftIterator.hasNext()) {
                    leftObject = leftIterator.next();
                } else {
                    result.add(rightObject);
                    while (rightIterator.hasNext()) {
                        result.add(rightIterator.next());
                    }
                    break;
                }
            } else {
                result.add(rightObject);
                if (rightIterator.hasNext()) {
                    rightObject = rightIterator.next();
                } else {
                    result.add(leftObject);
                    while (leftIterator.hasNext()) {
                        result.add(leftIterator.next());
                    }
                    break;
                }
            }
        }
        return result;
    }

    public static void main(String args[]) {
        ArrayList<Integer> arr = new ArrayList<Integer>();
        for (int i = 0; i < 10; i++) {
            int num = (int) (Math.random() * 100);
            arr.add(num);
        }
        System.out.println(arr);
        //System.out.println(quickSort(arr));
        System.out.println(mergeSort(arr));

    }
}
